package com.hardy.data_structure;

/**
 * Author: Hardy
 * Date:   2019/3/21
 * Description:
 **/
public class SingleLinked extends Linked {

    public void add(int val) {
        Node node = new Node(val);

        if (root == null) {
            root = node;
        } else {
            Node pre = root;

            while (pre.next != null) {
                pre = pre.next;
            }
            pre.next = node;
        }
        length++;
    }

    public void del(int val) {
        if (root == null) return;

        Node pre = null;
        Node node = root;

        while (node.val != val) {
            pre = node;
            node = node.next;
        }

        if (pre == null) {
            root = node.next;
        } else {
            pre.next = node.next;
        }
        length--;
    }

    public void insert(int idx, int val) {
        if (idx < 0 || idx > length) {
            System.out.println("不合法位置");
            return;
        }

        Node node = new Node(val);

        // 没有头结点插入
        if (root == null) {
            root = node;
            length++;
            return;
        }

        // 有头结点插入
        Node pre = null;
        Node next = root;
        for (int i = 0; i < idx; i++) {
            pre = next;
            next = next.next;
        }

        if (pre != null)
            pre.next = node;
        else
            root = node;

        node.next = next;
        length++;


//        // 头结点插入
//        if (idx == 0) {
//            node.next = root;
//            root = node;
//            length++;
//            return;
//        }
//
//        Node pre = root;
//        for (int i = 1; i < idx; i++) {
//            pre = pre.next;
//        }
//
//        node.next = pre.next;
//        pre.next = node;
//        length++;
    }

    public void remove(int idx) {
        if (idx < 0 || idx >= length) {
            System.out.println("不合法位置");
            return;
        }

        Node pre = null;
        Node node = root;
        for (int i = 0; i < idx; i++) {
            pre = node;
            node = node.next;
        }

        if (pre == null)
            root = node.next;
        else
            pre.next = node.next;

//        // 头结点
//        if (idx == 0) {
//            root = root.next;
//            length--;
//            return;
//        }
//
//        Node pre = root;
//        for (int i = 1; i < idx; i++) {
//            pre = pre.next;
//        }
//
//        if (pre.next != null)
//            pre.next = pre.next.next;

        length--;
    }

    public void reverse() {
        if (root == null) return;

        Node pre = null;
        Node node = root;
        while (node != null) {
            Node next = node.next;

            // 反转
            node.next = pre;

            // 偏移
            pre = node;
            node = next;
        }
        root = pre;
    }

    public boolean checkCircle() {
        if (root == null) return false;

        Node slow = root;
        Node fast = root;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) return true;
        }
        return false;
    }
}
